题面传送门：P16487 [GKS 2014 #C] Taking Metro
题目大意
给定两个地铁站，求它们之间的最短通勤时间。
思路讲解
从题面中不难看出，这本质上是道求最短路的题，而这道题的难点在于建图。
我们可以把时间当作边权，这道题对时间的描述就分别有：
- 车站间的运行时间
- 换乘通道的步行时间
- 预期的等待时间
对于前两种描述，我们直接把两个站点连起来，以时间为边权，建边就完成了。
第三种描述看起来类似点权，我们熟知的最短路算法并不能简单地处理点权。因此可以考虑把预期等待时间也转成边来处理。
转化具体思路
常识中，我们要在地铁 号线的站台上等候 分钟，然后登上地铁列车。这里的 分钟可以说你一直在同一个点。
现在把它改成：地铁一直在那里，且可以一直等着我们，但我们走得很慢，需要 分钟才能走上车。这里的 分钟，你从站台走上了车，相当于走出了一条边。
综上可以将一个地铁车站分为两部分（站台和车上），对这两部分连边即可。
处理完跑最短路即可。
代码实现
最短路算法的选择
先计算一下这个图的最大点数 和最大边数 ：
每个测试用例中的车站总数不超过 ，一站分为两部分，所以 。
每个站有两部分，每站各部分之间有无向边，即 条有向边；外加每组相邻站有无向边，即最多 条边，所以 约为 。
题目还是多测，，别说 Floyd 了，直接跑 遍甚至 遍（不带车上点）加堆优化的 Dijkstra 也过不了。但题目中 的范围可以让我们在每次询问的时候跑 Dijkstra 算法，这样就可以通过了。
存储
存储可用链式前向星和邻接表。线路、是否上车、站点号的处理若要通过所有数据，则可以通过创建映射表的方法来解决。主要思想就是赋予每个站一个编号，特别的，不在车上的编号为站点编号 ，以达到一分区一编号的效果。
for(int i=1;i<=n;i++){ cin>>sn[i]>>w[i]; for(int j=1;j<=sn[i];j++){ num++; mp[make_pair(i,j)]=num; if(j!=sn[i]){ cin>>ti; add(mp[make_pair(i,j)],mp[make_pair(i,j)]+1,ti); add(mp[make_pair(i,j)]+1,mp[make_pair(i,j)],ti); //两站站内之间建双向边 } add(mp[make_pair(i,j)],mp[make_pair(i,j)]+1000,0); add(mp[make_pair(i,j)]+1000,mp[make_pair(i,j)],w[i]); //当前站站内外建双向边 }}完整代码
#include<bits/stdc++.h>using namespace std;int t,n,sn[105],w[105],ti,m,m1,s1,m2,s2,tr,qu,x1,yl,x2,y2;int cnt,to[4005],val[4005],nxt[4005],h[2005];int num,dis[2005],uu,vv,num1,num2;bool b[2005];map<pair<int,int>,int>mp;priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;void add(int a,int b,int c){ cnt++; to[cnt]=b; val[cnt]=c; nxt[cnt]=h[a]; h[a]=cnt;}int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>t; for(int z=1;z<=t;z++){ cin>>n; memset(h,0,sizeof(h));//不清空会导致66行死循环 num=0;cnt=0;//多测不清空，爆零两行泪 for(int i=1;i<=n;i++){ cin>>sn[i]>>w[i]; for(int j=1;j<=sn[i];j++){ num++; mp[make_pair(i,j)]=num; if(j!=sn[i]){ cin>>ti; add(mp[make_pair(i,j)],mp[make_pair(i,j)]+1,ti); add(mp[make_pair(i,j)]+1,mp[make_pair(i,j)],ti); //两站站内之间建双向边 } add(mp[make_pair(i,j)],mp[make_pair(i,j)]+1000,0); add(mp[make_pair(i,j)]+1000,mp[make_pair(i,j)],w[i]); //当前站站内外建双向边 } } cin>>m; for(int i=1;i<=m;i++){ cin>>m1>>s1>>m2>>s2>>tr; add(mp[make_pair(m1,s1)]+1000,mp[make_pair(m2,s2)]+1000,tr); add(mp[make_pair(m2,s2)]+1000,mp[make_pair(m1,s1)]+1000,tr); //站外换乘通道建双向边 } //补药在此处预处理最短路！会TLE cin>>qu; cout<<"Case #"<<z<<":\n"; for(int k=1;k<=qu;k++){ cin>>x1>>yl>>x2>>y2; num1=mp[make_pair(x1,yl)]+1000;num2=mp[make_pair(x2,y2)]+1000; for(int i=1;i<=1000+num;i++){ dis[i]=0x3fffffff; b[i]=0; } dis[num1]=0; q.push(make_pair(0,num1)); while(!q.empty()){ uu=q.top().second; q.pop(); if(b[uu]==1) continue; b[uu]=1; for(int j=h[uu];j!=0;j=nxt[j]){//这里是66行 vv=to[j]; if(dis[vv]>dis[uu]+val[j]){ dis[vv]=dis[uu]+val[j]; q.push(make_pair(dis[vv],vv)); } } } cout<<' '; if(dis[num2]==0x3fffffff){ cout<<"-1\n"; }else{ cout<<dis[num2]<<'\n'; } } } return 0;}